[luogu 3355] 骑士共存问题

原题链接:[luogu 3355] 骑士共存问题
题目大意:有一个nnn*n的棋盘,上面规定了mm个点是被破坏了的,不能在上面放置棋子.每个棋子可以按象棋中"日"字型的方式移动,问整个棋盘上最多可以放置多少个互不攻击的棋子.
数据范围:
1n2001 \leq n \leq 200
1m<nn1 \leq m < n * n

假如说把这个棋盘进行二染色,即染成下面这样:

那么对于一个棋子如果他所在的位置的颜色是红色,那么他走"日"字能到达的点一定是绿色;反之亦然.这是因为如果走偶数条路颜色相同,再多走一步显然颜色不同.因此整张棋盘可以二染色.对于原图的坐标来说,如果坐标之和为奇数,那么是绿色,反之就是红色.
在二染色之后,如果把所有的点按照绿色连红色的二分图来看的话,就相当于在这张图上求一个最大独立集,即最多能选多少个互不相连的点.根据结论:最大独立集=点数-最大匹配数.求出这张图的最大匹配即可求出.不过这张图上还有一些点被破坏了,所以计算答案的时候还需要额外的去掉有多少个点被破坏掉了.
考虑求最大匹配数:本题据说可以匈牙利过掉,不过我的匈牙利只有36分,很奇怪.这里给出最大流求解的方式.建图比较明显,就是源点为00连向所有的左部点,汇点为nn+1n*n+1被所有的右部点链接.每个绿色的点出发有八个方向的拓展点,连接即可.三种关系的流量都是11.求最大流即可.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205 * 205,M = 2e6+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N],forbid[205][205],g[205][205];
ll incf[N],maxflow;
queue<int> q;
const int dx[8] = {-2,-2,-1,1,2,2,1,-1},dy[8] = {-1,1,2,2,1,-1,-2,-2};
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	scanf("%d%d",&n,&m);
	s = 0,t = n * n + 1;
	for(int i = 0;i < m;++i)
	{
		int x,y;scanf("%d%d",&x,&y);
		forbid[x][y] = 1;
	}
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
		{
			if(forbid[i][j])	continue;
			if((i + j) % 2 == 1)
			{
				int u = (i - 1) * n + j;
				add(s,u,1);
				for(int _ = 0;_ < 8;++_)
				{
					int a = i + dx[_],b = j + dy[_];
					if(a < 1 || a > n || b < 1 || b > n || forbid[a][b])	continue;
					int v = (a - 1) * n + b;
					add(u,v,1);
				}
			}
			else 
			{
				int v = (i - 1 ) * n + j;
				add(v,t,1);
			}
		}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	printf("%lld",n * n - m - maxflow);
    return 0;
}